Modular multiplicative inverse - function in MiniZinc?

Andrew Gill

unread,

May 2, 2025, 2:45:48 PMMay 2

to MiniZinc

Hi - I need to compute the inverse of n mod N. I have pseudo-code (below), but the functions I have seen in MiniZinc seem to be 'one-liners', so I don't know how to implement things like while loops, if and return statements.

I was hoping this function 'existed' somewhere, but I haven't been able to find it. Any pointers greatly accepted!

function inverse(n,N)

s=0; s'=1;

r=N; r'=n

while (r'\neq 0) do

q=r div r';

temp=s';

s'=s-q*temp;

s=temp;

temp=r';

r'=r-q*temp;

r=temp;

endwhile

if(s<0) s=s+N;

return(s)

guido.tack

unread,

May 6, 2025, 12:24:03 PMMay 6

to MiniZinc

You could express this directly using the modulo operator:

function var int: mod_inverse(var int: n, var int: N) =
let {
var 1..ub(N)-1: result;
constraint (n * result) mod N = 1 /\
result <= N - 1 /\
result >= 1;
} in result;

Note that this is a partial function, since it's only defined for values of n and N that are coprime. This means that the function will constrain its arguments, e.g.

var 1..10: x;

var 1..10: y;

var int: z = mod_inverse(x, y);

not only constrains z to be the inverse, but it also constrains x and y to be coprime.

Cheers,

Guido

Andrew Gill

unread,

May 6, 2025, 7:07:07 PMMay 6

to MiniZinc

Thanks Guido. Unfortunately, I would need to use that via:

function var int: mod_inverse(var int: a, var int: N) =

let {

var 1..ub(N)-1: result;

constraint (a * result) mod N = 1 /\

result <= N - 1 /\

result >= 1;

} in result;

constraint forall([n_inv[j] = mod_inverse(n[j],N) | j in 2..k]);

and that seems to throw an error:

in binary '=' operator expression

in call 'mod_inverse'

in let expression

in variable declaration for 'result'

in binary '..' operator expression

I presume because I have var int: N; (a non-finite declared type) and the ub() doesn't like this?

I think however I can use:

constraint forall([n[j]*n_inv[j]+N*y[j]=1 | j in 2..k]);

constraint forall([n_inv[j]>=1 | j in 2..k]);

constraint forall([n_inv[j]<=N-1 | j in 2..k]);

albeit at the expense of having to declare a variable array y (that I don't actually use).

guido.tack

unread,

May 7, 2025, 4:21:41 AMMay 7

to MiniZinc

The ub(N)-1 is an optimisation, the function would also work with var 1..infinity: result. However, since none of the MiniZinc solvers can really deal well with unbounded variables, it would probably be better to give N some reasonable bounds, if possible.